package com.lims.algorithm.algset.heap;

/**
 * <功能简述>二项堆
 * -----------------------------------------------------------
 * 二项堆是二项树的集合,遵循最小堆性质。（此处高度从0开始）
 * 二项堆H的定义：
 * 1.H中每个二项树都是最小堆；
 * 2.对任意非负整数k，在H中至多有一棵二项树的根具有度数K。
 * <p>
 * 二项堆的第(01)个性质保证了二项堆的最小节点就是某个二项树的根节点，
 * 第(02)个性质则说明结点数为n的二项堆最多只有log{n} + 1棵二项树。
 * 实际上，将包含n个节点的二项堆，表示成若干个2的指数和(或者转换成二进制)，则每一个2个指数都对应一棵二项树。
 * 例如，13(二进制是1101)的2个指数和为13=2^3 + 2^2+ 2^0, 因此具有13个节点的二项堆由度数为3, 2, 0的三棵二项树组成。
 * -----------------------------------------------------------
 * 二项树递归定义：
 * 1.二项树B0有一个结点；
 * 2.二项树Bk由两棵B(k-1)组成，其中一棵树是另一棵树根的最左孩子（结点按二项分布）
 * -----------------------------------------------------------
 * 二项树Bk有以下性质：
 * <p>
 * 1) 共有2^k个结点
 * <p>
 * 2) 树的高度为k
 * <p>
 * 3) 在深度i处恰有C_k^i个结点，其中i=0,1,2,...,k
 * <p>
 * 4) 根的度数为k，它大于任何其它结点的度数；并且，如果根的子女从左到右编号为k-1,k-2,...,0，子女i是子树Bi的根。
 * <p>
 * 在一棵包含n个结点的二项树中，任意结点的最大度数为lgn。
 * -----------------------------------------------------------
 *
 * @author lims
 * @date 2020-07-23 15:16
 */
public class BinomialHeap<T extends Comparable<T>> {
    class BinomialNode<T extends Comparable<T>> {
        // 关键字
        T key;
        // 度数
        int degree;
        // 左孩子
        BinomialNode<T> child;
        // 父节点
        BinomialNode<T> parent;
        // 兄弟节点
        BinomialNode<T> next;

        public BinomialNode(T key) {
            this.key = key;
            this.degree = 0;
            this.child = null;
            this.parent = null;
            this.next = null;
        }

        @Override
        public String toString() {
            return "key:" + key;
        }
    }

    /**
     * 根节点
     */
    BinomialNode<T> mRoot;

    /**
     * 合并二项堆的根链表，按“单调递增”
     *
     * @param h1
     * @param h2
     * @return
     */
    private BinomialNode<T> merge(BinomialNode<T> h1, BinomialNode<T> h2) {
        if (h1 == null) {
            return h2;
        }
        if (h2 == null) {
            return h1;
        }

        if (h1.degree < h2.degree) {
            h1.next = merge(h1.next, h2);
            return h1;
        } else {
            h2.next = merge(h1, h2.next);
            return h2;
        }
    }

    /**
     * 合并两个二项树：将child合并到root
     *
     * @param child
     * @param root
     */
    private void link(BinomialNode<T> child, BinomialNode<T> root) {
        child.parent = root;
        child.next = root.child;
        root.child = child;
        root.degree++;
    }

    /**
     * 合并二项堆
     * <p>
     * merge函数：合并根链
     * link函数：辅助函数，将"二项堆child的根节点"设为"二项堆root的左孩子"，从而将child整合到root中去。
     * <p>
     * 合并算法：
     * 1.在combine(h1, h2)中对h1和h2进行合并时；
     * 首先通过 merge(h1, h2) 将h1和h2的根链表合并成一个"按节点的度数单调递增"的链表；
     * 2.然后进入while循环，对合并得到的新链表进行遍历，将新链表中"根节点度数相同的二项树"连接起来，直到所有根节点度数都不相同为止。
     * PS：在将新联表中"根节点度数相同的二项树"连接起来时，可以将被连接的情况概括为4种。
     * （1）x->degree != next_x->degree
     * -             即，"当前节点的度数"与"下一个节点的度数"不相等时。此时，不需要执行任何操作，继续查看后面的节点。
     * （2）x->degree == next_x->degree == next_x->next->degree
     * -             即，"当前节点的度数"、"下一个节点的度数"和"下下一个节点的度数"都相等时。
     * -             此时，暂时不执行任何操作，还是继续查看后面的节点。
     * -             实际上，这里是将"下一个节点"和"下下一个节点"等到后面再进行整合连接。
     * （3）x->degree == next_x->degree != next_x->next->degree
     * -        && x->key <= next_x->key
     * -             即，"当前节点的度数"与"下一个节点的度数"相等，并且"当前节点的键值"<="下一个节点的度数"。
     * -             此时，将"下一个节点(对应的二项树)"作为"当前节点(对应的二项树)的左孩子"。
     * （4）x->degree == next_x->degree != next_x->next->degree
     * -        && x->key > next_x->key
     * -             即，"当前节点的度数"与"下一个节点的度数"相等，并且"当前节点的键值">"下一个节点的度数"。
     * -             此时，将"当前节点(对应的二项树)"作为"下一个节点(对应的二项树)的左孩子"。
     *
     * @param h1
     * @param h2
     * @return
     */
    public BinomialNode<T> combine(BinomialNode<T> h1, BinomialNode<T> h2) {
        BinomialNode<T> root;

        // 将h1, h2中的根表合并成一个按度数递增的链表root
        root = merge(h1, h2);
        if (root == null) {
            return null;
        }

        BinomialNode<T> prev_x = null;
        BinomialNode<T> x = root;
        BinomialNode<T> next_x = x.next;

        while (next_x != null) {
            if ((x.degree != next_x.degree) ||
                    ((next_x.next != null) && (next_x.degree == next_x.next.degree))) {
                // Case1.x.degree != next_x.degree
                // Case2: x.degree == next_x.degree == next_x.next.degree
                prev_x = x;
                x = next_x;
            } else if (x.key.compareTo(next_x.key) <= 0) {
                //  Case 3: x.degree == next_x.degree != next_x.next.degree
                //      && x.key    <= next_x.key
                x.next = next_x.next;
                link(next_x, x);
            } else {
                //Case 4: x.degree == next_x.degree != next_x.next.degree
                //        && x.key    >  next_x.key
                if (prev_x == null) {
                    root = next_x;
                } else {
                    prev_x.next = next_x;
                }
                link(x, next_x);
                x = next_x;
            }
            next_x = x.next;
        }

        return root;
    }

    /**
     * 将二项堆other合并到当前堆中
     *
     * @param other
     */
    public void combine(BinomialHeap<T> other) {
        if (other != null && other.mRoot != null) {
            mRoot = combine(mRoot, other.mRoot);
        }
    }

    /**
     * 插入
     */
    public void insert(T key) {
        BinomialNode<T> node;

        // 禁止插入相同的键
        if (contains(key)) {
            System.out.printf("insert failed: the key(%s) is existed already!\n", key);
            return;
        }

        node = new BinomialNode<>(key);
        if (node == null) {
            return;
        }

        mRoot = combine(mRoot, node);
    }

    /**
     * 递归搜索二项堆中的结点
     *
     * @param root
     * @param key
     * @return
     */
    private BinomialNode<T> search(BinomialNode<T> root, T key) {
        BinomialNode<T> child;
        BinomialNode<T> parent = root;

        while (parent != null) {
            if (key.compareTo(parent.key) == 0) {
                return parent;
            } else {
                if ((child = search(parent.child, key)) != null) {
                    return child;
                }
                parent = parent.next;
            }
        }
        return null;
    }

    /**
     * 二项堆中是否包含键值key
     */
    public boolean contains(T key) {
        return search(mRoot, key) != null ? true : false;
    }


    /**
     * 打印堆信息
     */
    private void print(BinomialNode<T> node, BinomialNode<T> prev, int direction) {
        while (node != null) {
            if (direction == 1) {
                // node是根节点
                System.out.printf("\t%2d(%d) is %2d's child\n", node.key, node.degree, prev.key);
            } else {
                // node是分支节点
                System.out.printf("\t%2d(%d) is %2d's next\n", node.key, node.degree, prev.key);
            }

            if (node.child != null) {
                print(node.child, node, 1);
            }

            // 兄弟节点
            prev = node;
            node = node.next;
            direction = 2;
        }
    }


    public void print() {
        if (mRoot == null) {
            return;
        }

        BinomialNode<T> p = mRoot;
        System.out.printf("== 二项堆( ");
        // 打印根链表信息
        while (p != null) {
            System.out.printf("B%d ", p.degree);
            p = p.next;
        }
        System.out.printf(")的详细信息：\n");

        int i = 0;
        p = mRoot;
        // 打印每颗二项树
        while (p != null) {
            i++;
            System.out.printf("%d. 二项树B%d: \n", i, p.degree);
            System.out.printf("\t%2d(%d) is root\n", p.key, p.degree);

            print(p.child, p, 1);
            p = p.next;
        }
        System.out.printf("\n");
    }

    /************************************************************/

    public static void main(String[] args) {
        // 共7个 = 1+2+4
        int[] a = {12, 7, 25, 15, 28, 33, 41};
        // 共13个 = 1+4+8
        int[] b = {18, 35, 20, 42, 9, 31, 23, 6, 48, 11, 24, 52, 13};

        // 验证"二项堆的插入操作"
        BinomialHeap<Integer> bha = new BinomialHeap<>();
        // 二项堆bha
        System.out.printf("== 二项堆(ha)中依次添加: ");
        for (int i = 0; i < a.length; i++) {
            System.out.printf("%d ", a[i]);
            bha.insert(a[i]);
        }
        System.out.printf("\n");
        System.out.printf("== 二项堆(ha)的详细信息: \n");
        bha.print();

    }
}






















